\documentclass{article}
\usepackage{polski}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\usepackage[usenames,dvipsnames]{color} % For colors and names
\usepackage{amsmath}
\usepackage{graphicx}
\title{Laboratorium Rozpoznawania Obrazów \\ ćwiczenie 3-4: klasyfikatory liniowe w~rozpoznawaniu ręcznego pisma blokowego } % Title


\textwidth = 400pt
\oddsidemargin = 30pt
\hyphenpenalty = 1000

\author{Tomasz \textsc{Bawej}} % Author name

\definecolor{mygrey}{gray}{.96} % Light Grey
\lstset{language=Verilog, tabsize=3, backgroundcolor=\color{mygrey}, basicstyle=\small \ttfamily, commentstyle=\color{BrickRed}}
\lstset{ 
	language=[ISO]C++,              % choose the language of the code ("language=Verilog" is popular as well)
   tabsize=3,							  % sets the size of the tabs in spaces (1 Tab is replaced with 3 spaces)
	basicstyle=\scriptsize,               % the size of the fonts that are used for the code
	numbers=left,                   % where to put the line-numbers
	numberstyle=\scriptsize,              % the size of the fonts that are used for the line-numbers
	stepnumber=2,                   % the step between two line-numbers. If it's 1 each line will be numbered
	numbersep=5pt,                  % how far the line-numbers are from the code
	backgroundcolor=\color{mygrey}, % choose the background color. You must add \usepackage{color}
	%showspaces=false,              % show spaces adding particular underscores
	%showstringspaces=false,        % underline spaces within strings
	%showtabs=false,                % show tabs within strings adding particular underscores
	frame=single,	                 % adds a frame around the code
	tabsize=3,	                    % sets default tabsize to 2 spaces
	captionpos=b,                   % sets the caption-position to bottom
	breaklines=true,                % sets automatic line breaking
	breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
	%escapeinside={\%*}{*)},        % if you want to add a comment within your code
	commentstyle=\color{BrickRed},   % sets the comment style
	columns=fixed
}

\begin{document}

\maketitle % Insert the title, author and date

%\begin{tabular}{lr}
%Date Performed: 1/1/2012 & Partner: James Smith\\ % Date the experiment was performed and partner's %name
%Instructor: Mary Jones % Instructor/supervisor
%\end{tabular}

\setlength\parindent{0pt} % Removes all indentation from paragraphs

\renewcommand{\labelenumi}{\alph{enumi}.} % Make numbering in the enumerate environment by letter rather than number (e.g. section 6)

\section{Opis metody klasyfikacji znaków przy użyciu klasyfikatorów liniowych.}

Opisywane rozwiązanie umożliwia klasyfikację znaków na cztery sposoby:
\begin{itemize}
\item \textit{one-vs-all} - wykorzystujący zestaw 10 klasyfikatorów, z których każdy ma za zadanie określić miarę podobieństwa analizowanej próbki do jednej z klas wzorcowych. Wybrana zostaje klasa o najlepszym wyniku.
\item \textit{head-to-head (lazy)} - wykorzystujący 10 z 45 klasyfikatorów umożliwiających rozróżnianie poszczególnych klas pomiędzy sobą. Z grona potencjalnych klas kolejno eliminuje się gorszą spośród dwóch pierwszych, aż do momentu ograniczenia liczby kandydatów do 1.
\item \textit{head-to-head (exhaustive)} - wykorzystujący 45 klasyfikatorów i ligowy system wyłaniania zwycięzcy.
\item mieszany - polegający na wyznaczeniu grona potencjalnych klas za pomocą klasyfikatorów \textit{one-vs-all}, aby następnie drogą bezpośrednich porównań wyłonić zwycięzcę (leniwie lub wyczerpująco).
\end{itemize}

Funkcją odpowiedzialną za wskazanie właściwej klasy jest \textit{tellClass}. 

\section{Opis algorytmu wyznaczania parametrów płaszczyzny decyzyjnej.}
W fazie wyznaczania parametrów płaszczyzny decyzyjnej, każdemu z 55 klasyfikatorów prezentowany jest podzbiór danych trenujących właściwy ze względu na "obsługiwaną" przez klasyfikator hipotezę. Każda próbka jest w tym celu opisywana etykietą 1 lub 0 w zależności od pożądanej odpowiedzi klasyfikatora, a cała przestrzeń cech rozszerzona o jedną stałą cechę o wartości 1. Ponadto, w ramach czynności wstępnych zadbano o wyrównanie proporcji pomiędzy próbkami poszczególnych klas (funkcja \textit{getMockData}).
Dla wektora cech $x$ oraz wektora współczynników $\theta$ wartość hipotezy wyrażona jest wzorem:
$$ h_\theta(x)=\frac{1}{1+e^(\theta^Tx)} $$

Jednocześnie koszt związany z błędem hipotezy wyznaczany jest według wzoru:
$$J(\theta)=-\frac{1}{m}[\sum_{i=1}^{m}y^{(i)}\log {h_\theta(x^{(i)})} 
	+(1-y^{(i)})\log{(1-h_\theta(x^{(i)}))}]$$
	gdzie $m$ jest liczbą przykładów, a $y$ pożądaną odpowiedzią klasyfikatora.
	W celu minimalizacji powyższego kosztu i tym samym wyznaczenia optymalnych parametrów płaszczyzny decyzyjnej, wykorzystano regułę spadku gradientu, którą dla każdego z $j$ klasyfikatorów ilustruje zapis:
$$ \theta_j := \theta_j - \alpha\frac{\partial J(\theta)}{\partial \theta_j} $$
	gdzie $\alpha$ oznacza wektor współczynników uczenia.
	Dla zdefiniowanej powyżej funkcji kosztu, aktualizacja parametrów płaszczyzny decyzyjnej przybiera postać:
$$ \theta_j := \theta_j - \alpha \sum_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)} $$

Proces ten został zaimplementowany w funkcji \textit{gradientDescent}, przyjmującej następujące parametry (notacja \textit{Octave}, znak "=" poprzedza wartość domyślną):
\begin{itemize}
\item \textit{data}, \textit{labels}, \textit{initParams}, \textit{lr=3} - dane, etykiety, początkowe parametry klasyfikatora, początkowa wartość współczynników uczenia.
\item \textit{vdata=[]} - zbiór danych walidujących, zawierający etykiety w pierwszej kolumnie. Umożliwia obserwację zmian jakości klasyfikacji całego systemu klasyfikatorów w~poszczególnych iteracjach.
W zaimplementowanym rozwiązaniu zastosowano wektor adaptacyjnych współczynników uczenia, których wartości zmieniają się w zależności od~znaku iloczynu następujących kolejno po~sobie pochodnych funkcji kosztu związanych z~danym parametrem.
\item \textit{allParams=[]}, \textit{paramsInd=-1} - macierz parametrów wszystkich płaszczyzn decyzyjnych pełnego zbioru klasyfikatorów oraz numer wiersza identyfikujący bieżący klasyfikator. Konieczne dla przeprowadzania globalnej walidacji.
\item \textit{iterations=100, stagLimit=6} - parametry używane do wyznaczania kryterium stopu. W~razie braku danych walidujących, wiążąca jest liczba iteracji. W~przypadku korzystania ze zbioru walidującego, uczenie zostaje przerwane, kiedy w przeciągu odpowiedniej liczby iteracji algorytm nie zanotuje postępu. Wartość progowa kryterium stagnacji zmienia się wraz z rosnącą liczbą wykonanych iteracji, jak na rys. \ref{fig:stagLimit}.
\begin{figure}[htc]
\includegraphics[width=\linewidth]{stagLimit.png} 
\caption{Zależność progu kryterium stagnacji od liczby wykonanych iteracji dla 100 domyślnych iteracji oraz minimalnej progowej wartości równej 6.}
\label{fig:stagLimit}
\end{figure}
\item \textit{sensitivityThreshold=0.0001} - próg (nie)czułości na sumaryczną wartość pochodnej błędu w algorytmie spadku gradientu. Osiągnięcie zadanego poziomu przerywa uczenie.\
\end{itemize}

Funkcja \textit{gradientDescent} jest dla każdego klasyfikatora wywoływana z funkcji \textit{getDecPlane}, gdzie zachodzi także podział danych na część walidującą oraz ściśle treningową.

\section{Jakość klasyfikatorów}

Poniżej zebrano wyniki i obserwacje dla dwóch względnie udanych eksperymentów (jakość klasyfikacji ok. 90\%).
\input{eksperyment1.tex}
\input{eksperyment2.tex}
\subsection{Podsumowanie}
Na podstawie powyższych wyników łatwo zauważyć, że system klasyfikatorów \textit{one-vs-all} wyraźnie nie jest najszczęśliwszym wyborem do zadania rozpoznawania cyfr. Systemy porównujące bezpośrednio poszczególne klasy, mimo iż znacznie efektywniejsze, generują natomiast istotny narzut obliczeniowy. Ten można jednak przenieść niemal całkowicie na etap trenowania klasyfikatora dzięki wykorzystaniu "leniwego" odpytywania. Pociąga to~jednak za~sobą nieznaczny spadek jakości klasyfikacji względem zmierzonej dla odpytywania wg~modelu ligowego.
Osiągniętą jakość klasyfikacji dało by~się zapewne jeszcze nieznacznie podnieść na~drodze eksperymentowania z liczbą wymiarów, rozmiarem danych treningowych i liczbą wykonanywanych iteracji. Ciężko jednak oczekiwać poprawy na tyle znacznej, aby warto było kontynuować eksperymenty. (Choćby dlatego, że zbadane zestawy klasyfikatorów uczone dziesiątą częścią danych trenujących odznaczały się jakością klasyfikacji do 2\% gorszą od~odpowiadających im klasyfikatorów trenowanych na połowie i więcej danych.)\\\\
Uzyskane parametry płaszczyzn decyzyjnych zostały zapisane w plikach \textit{params\_exp1} oraz \textit{params\_exp2}.


\section{Wyznaczanie poziomu ufności}
Wykorzystany w fazie uczenia zestawu klasyfikatorów zbiór walidujący pozwala całkiem dobrze estymować jakość klasyfikacji, aczkolwiek generowany podczas treningu wynik ignoruje warunkowe prawdopodobieństwa błędu dla poszczególnych odpowiedzi klasyfikatorów. Problem ten można rozwiązać zwracając z funkcji \textit{getDecPlane} dodatkową wartość w postaci zbioru walidującego wykorzystywanego w~procesie uczenia klasyfikatora. Umożliwia to następnie uzyskanie macierzy błędów odpowiadającej wybranemu ostatecznie sposobowi klasyfikacji. Podzielenie maksymalnej wartości występującej w każdej kolumnie przez sumę wartości z tej kolumny (pod warunkiem, że~maksimum faktycznie odpowiada właściwej klasie) pozwala uzyskać estymację warunkowego prawdopodobieństwa podjęcia słusznej decyzji pod warunkiem wskazania konkretnej klasy. Ilustruje to poniższy listing, na którym zamieszczono wynik porównania prawdopodobieństw warunkowych podjęcia słusznej decyzji dla zbiorów: walidującego oraz testowego.



\begin{lstlisting}[caption=Szacowany poziom ufności a jakość klasyfikacji.]
>[params vdata] = getDecPlane(mtd, mtl, 20, 1);
>[score errmx]=verify(vdata(:,2:end),vdata(:,1),params);
>[score2 errmx2]=verify(ed,el,params);
>(max(errmx)(1,1:end-1)./sum(errmx)(1,1:end-1)) ./ 
	(max(errmx2)(1,1:end-1)./sum(errmx2)(1,1:end-1))
#dla 15/100 zbioru treningowego otrzymano:
1.0025  0.9510  0.9783  0.9991  1.0302  1.0670  0.9771  1.0035  1.0058  1.0569
#to samo dla 4/10 oryginalnego zbioru treningowego:
1.0470  0.9690  1.0172  0.9794  1.0054  1.0060  1.0029  1.0174  1.0329  0.9628

\end{lstlisting}  

Powyższe wyniki uzyskano wykorzystując w charakterze danych treningowych odpowiednio 15\% i 40\% oryginalnego zbioru treningowego i pomimo, iż dla większych zbiorów rozbieżności zapewne będą mniejsze, to~można zastosować dodatkowy zabieg, częściowo zaimplementowany w funkcji \textit{leaveOneOut}. Funkcja ta dzieli zbiór treningowy na zadaną parametrem liczbę podzbiorów $n$, po~czym na~każdej kombinacji $n-1$ podzbiorów przeprowadza osobny trening zakończony weryfikacją na~jedynym niewyokorzystanym w danej iteracji podzbiorze. Dla~ porównania przeprowadzany jest także proces weryfikacji jakości względem zbioru testowego. Funkcja bada jedynie ogólny odsetek błędów przy odpytywaniu sposobem mieszanym z "leniwym" rozstrzyganiem konfliktów. W~ostatniej, $n+1$-ej iteracji funkcja trenuje klasyfikatory na całym zbiorze trenującym, szacuje ufność jako średnią z dotychczas uzyskanych wyników oraz dla porównania oblicza jakość klasyfikacji na pełnym zbiorze testowym. Dla 10\% danych treningowych oraz $n$=3 uzyskano następujące wyniki:

\begin{table}[htc]
\centering
\begin{tabular}{|c|c|c|}
\hline 
iteracja & szacowana ufność & jakość klasyfikacji \\ 
\hline 
1 & 0.89242 & 0.88440 \\ 
\hline 
2 & 0.87513 & 0.88390 \\ 
\hline 
3 & 0.89137 & 0.88650 \\ 
\hline 
-- & 0.88631 & 0.88560 \\ 
\hline 
\end{tabular} 
\end{table}

Prawdopodobnie najlepszym, przynajmniej z punktu widzenia szacowania ufności klasyfikatorów, rozwiązaniem było by trenowanie ich na pełnym zbiorze treningowym z wykorzystaniem funkcji \textit{leaveOneOut} rozszerzonej  o możliwość szacowania ufności warunkowej. Niestety, dla opisanego zestawu klasyfikatorów zabieg taki mógłby potrwać do kilkunastu godzin.

%----------------------------------------------------------------------------------------
%	BIBLIOGRAPHY
%----------------------------------------------------------------------------------------

%\begin{thebibliography}{9}

%\bibitem{Smith:2012qr}
%Smith, J.~M. and Jones, A.~B. (2012).
%\newblock {\em Chemistry}.
%\newblock Publisher, City, 7th edition.

%\end{thebibliography}

\end{document}
